P4198 楼房重建

P4198 楼房重建

题意

考虑在一个二维平面上,x 轴表示在一条直线上大楼排列的坐标,y 轴表示大楼的高度,那么第 ii 栋大楼可以用 (i,hi)(i,h_i) 表示。如果第 ii 栋大楼与第 jj 栋大楼满足 i<ji<jhiihjj\frac{h_i}{i}\geq\frac{h_j}{j},那么第 jj 栋大楼被第 ii 栋大楼挡住而不可视见。求从 (0,0)(0,0) 最多能看到的大楼数量。

阅读全文 »